from typing import List


class Solution:
    # 可以是可以，就是会超时
    def changeDFS(self, amount: int, coins: List[int]) -> int:
        coins.sort()
        res = 0
        
        # 回溯 + 剪枝
        def dfs(amount, i):
            if amount == 0:
                nonlocal res  #! 注意获取 res 权限！
                res += 1
                return
            for k in range(i, len(coins)):
                if amount - coins[k] >= 0:
                    dfs(amount-coins[k], k)
        
        dfs(amount, 0)
        return res
    
    def change(self, amount: int, coins: List[int]) -> int:
        # coins.sort()  # 甚至不需要排序！
        
        dp = [0] * (amount+1)
        dp[0] = 1

        for coin in coins:
            for i in range(coin, amount+1):
                dp[i] += dp[i-coin]
                
        return dp[amount]
